package lib

//link to 377 474
func init() {
	Probs = append(Probs, Problem{
		Num:         322,
		Discription: "凑成指定金额的最小硬币数",
		Level:       2,
		Labels: map[string]int{
			"动态规划": 1,
			"完全背包": 1,
			"空间降维": 1,
		},
	})
}

func CoinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)
	//默认置为-1，表示当前硬币种类不能组成当前值（因为要的是最小值，所以用默认值为0表示不可构成的话会出问题）
	for i := 1; i <= amount; i++ {
		dp[i] = -1
	}

	for i := 1; i <= len(coins); i++ {
		coin := coins[i-1]
		for j := 1; j <= amount; j++ {
			if coin == j {
				dp[j] = 1
			} else if coin < j {
				//先判断可以构成指定值后，再取最小
				if dp[j] != -1 && dp[j-coin] != -1 {
					dp[j] = min(dp[j], 1+dp[j-coin])
				} else if dp[j-coin] != -1 {
					dp[j] = 1 + dp[j-coin]
				}

			}
		}
	}

	return dp[amount]
}
